package offer;

import java.util.Arrays;

/**
 * @Author Elephas
 * @Date 2022/3/19
 **/
@FunctionalInterface
public interface FindKthLargest {
    int findKthLargest(int[] nums, int k);
}

class FindKthLargestImpl1 implements FindKthLargest{


    @Override
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        Arrays.sort(nums);
        return nums[n - k];
    }
}

class FindKthLargestTest{
    final static int[] TEST_01 = new int[]{3,2,1,5,6,4};

    public static void main(String[] args) {
        int n = TEST_01.length;
        for (int i = 0; i < n; i++) {
            System.out.println("i = "+ i +", nums[i] = " +
                    new FindKthLargestImpl2().findKthLargest(TEST_01, i + 1));
        }
    }
}

class FindKthLargestImpl2 implements FindKthLargest{

    @Override
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        return quickSelect(nums, n - k, 0, n - 1);
    }
    private int quickSelect(int[] nums, int k, int low, int high){
        int pos = partition(nums, low, high);
        if(pos == k){
            return nums[pos];
        }else if(pos > k){
            return quickSelect(nums, k, low, pos - 1);
        }else{
            return quickSelect(nums, k, pos + 1, high);
        }
    }
    private int partition(int[] nums, int low, int high){
        int pivot = nums[low];
        int left = low;
        for(int i = low + 1; i <= high; i++){
            if(nums[i] <= pivot){
                left++;
                int temp = nums[left];
                nums[left] = nums[i];
                nums[i] = temp;
            }
        }
        int temp = nums[left];
        nums[left] = pivot;
        nums[low] = temp;
        return left;
    }
}